Field of the Invention
This invention relates to task scheduling and task organization in processors.
Description of the Related Art
A real-time program is one that is guaranteed to respond correctly within a certain fixed time period after its task requirement is presented to it. This can include multiple task requirements, or even an ongoing stream of task requirements, each of which expects its response within a specified time of its pertinent data's being presented. Complex real-time programming may include pertinent data from asynchronously independent sources. Frequently, a real-time system may be required to respond in an unusual or speedy fashion to an “exceptional” datum, with or without abandoning its standard processing or output.
Real-time problems are not solved by processing speed alone. Processing speed determines the amount of time between the presentation of full input data, timing stimuli, and programming and the completion of calculations that determine an output dependent on those alone. Though the programming is usually fully present, the data and stimuli may depend on complex interactions that are not fully understood, especially in rare so-called “exceptional” cases. Full testing of a complex system is usually impossible, since combinations of variables increase exponentially in the number of variables, and permutations thereof (taking account of order) increase as a factorial. For example, of 10 variables there are 2^10=1,024 combinations, and 10!=3,628,800 permutations.
It has therefore long been clear that one critical requirement is to break down a real-time task into subtasks, each with few variables, that interact in a way about which conclusions can be drawn. This meshes well with the ability of multiple computing devices to communicate with one another, and with the recent development of individual computing chips that have multiple “cores,” each of which can be working on a different subtask at the same time. Even single cores permit independent response to different stimuli (interrupts) and multiple time-shared programs (multitasking). However, major difficulties have arisen in getting the benefit of these facts, which it will be the business of the present invention to address.
Each subtask must be real-time if the combination of them is to be real-time. But in practice a great dynamic range opens up between the expected response requirement of different subtasks. For example, an interrupt response may have to be less than a microsecond, while a database search may take 10 seconds or more—a factor of over seven “orders of magnitude” (common logarithmic units, or multipliers of 10). A slow task can delay the output of a fast task, which is clearly devastating. Task priorities attempt to deal with this, but are often counterproductive (priority inversion).
Rare, so-called “exceptional” cases, as mentioned above, may not only have a completely different time requirement but use completely different programming, and yet share the same system resources. All too often, orderly sidetracking or shutdown of the “normal” programming is a goal too complex to be solved. A crude reboot is the commonly observed sequel, whether in desktop computers or in modern, computerized city buses. In a high-value complex, whether a nuclear power plant or a steel mill, this is not an acceptable solution.
In addition to nesting of component real-time subtasks within a task, it is clearly desirable to have multiple tasks working side by side and scarcely affecting each other. This apparently simpler problem has also suffered difficulties, due to contests over shared resources, and the heaping up of tasks without discipline. Common experience includes the “stammering” of video and music on a home computer.
The use of multiple pre-emptive priorities in dealing with manifold real-time response requirements is well known. Customarily, the highest priority is denoted 0, and greater priority numbers denote lower priorities. When a higher priority process comes ready on a core, it can interrupt any running process of a lower priority, and can place itself on a processing queue of pending processes of its own priority. A typical design will reach for better real-time response by increasing the number of these priorities, sometimes as high as 256.
Because these processes must communicate with each other, complicated interactions are possible, including “priority inversion,” when a higher-priority process is effectively delayed by being dependent on a lower-priority one. This leads to design unpredictability. Because of this, another school of thought leans toward reducing the number of priorities as low as two (as in the Inmos Transputer, and in many common CPUs and embedded chips which offer uninterruptible Interrupt Service Routines or ISRs and a main program which can be interrupted by the ISRs). Recently some designers of XMOS have even gone as far as advocating only one priority on multicore chips which can serve independent stimuli with independent cores.
In any core that is running multiple processes, resources must be shared so that no process is “starved” or prevented from progressing. This leads to a requirement, at least in the lower priorities, for timeslicing so that one process's long loop does not exclude others of its own priority. Processes, especially high-priority ones, also yield place by blocking on communication.
Whatever their priority scheme, chips must be coded so as most effectively to use their response capabilities, a nontrivial development task to which much prior art has been dedicated on the part of both schools. (Compare “Rate Monotonic Analysis”, mentioned in U.S. Pat. No. 7,107,590.) Particularly rich have been the lines of development descending from the Inmos Transputer and its natively parallel language, occam. These have mastered both complex coding and data flows and, at the same time, cycle-counted response times to stimuli that give conclusive real-time results as long as the task requirement is not too demanding. However, the territory at which these meet—especially when multiple asynchronous stimuli may each have a real-time requirement—is not well covered and has typically been left to the complicated RTOS approaches of the first school, who also have been unsuccessful in giving a understandable and robust answer.
Systems with only one or two priorities can respond inefficiently for high-priority events when other tasks are time-consuming and cannot be timesliced rapidly. Systems with a large number of priorities have complexity problems. A time-consuming task can continually pre-empt and starve a task whose priority is slightly lower. Unresponsiveness of a low-priority task can “hang up” a high-priority task that is waiting on communication, or conversely, if the high-priority task is allowed to transmit its priority to the communication partner (priority inheritance), the latter can unexpectedly outrank and deadlock an unrelated third party. There has been no general methodology that allows multiple unrelated tasks with varying real-time requirements to efficiently use the resources of either a uniprocessor or a multicore processor.